package leetcode.code1851;

import java.util.Arrays;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * 执行用时：363 ms, 在所有 Java 提交中击败了6.12%的用户
 *
 * 内存消耗：100.3 MB, 在所有 Java 提交中击败了6.12%的用户
 *
 * 通过测试用例：42 / 42
 */
public class Solution0 extends Solution1851 {

	int LEFT = 0;
	int RIGHT = 1;

	@Override
	public int[] minInterval(int[][] intervals, int[] queries) {
		int[][] p = new int[intervals.length << 1][4];// *3 变 *2
		int pp = 0;
		for (int[] interval : intervals) {
			int L = interval[0];
			int R = interval[1];
			int size = R - L + 1;
			p[pp++] = new int[] { L, R, size, LEFT };
			p[pp++] = new int[] { R + 1, Integer.MAX_VALUE, Integer.MAX_VALUE, RIGHT };
		}
		Arrays.sort(p, (a, b) -> a[0] - b[0]);
		PriorityQueue<int[]> rightRge = new PriorityQueue<>((a, b) -> a[2] - b[2]);
		TreeMap<Integer, Integer> tm = new TreeMap<>();// <序号，最小区间>
//		tm.put(-1, -1);//较少一个if判断
		for (int[] cur : p) {
			int LR = cur[3], L = cur[0], size = cur[2];// , R = cur[1]
			int min = Math.min(size, tm.getOrDefault(L, Integer.MAX_VALUE));
			while (!rightRge.isEmpty() && rightRge.peek()[1] < L) {//
				rightRge.poll();
			}
			if (!rightRge.isEmpty()) {
				min = Math.min(min, rightRge.peek()[2]);
			}
			tm.put(L, min);
			if (LR == LEFT) {
				rightRge.add(cur);
			}
		}
		int len = queries.length;
		int[] ans = new int[len];
		for (int i = 0; i < len; i++) {
			Map.Entry<Integer, Integer> entry = tm.floorEntry(queries[i]);
			if (entry == null) {// tm.put(-1, -1);可顶替这个判空
				ans[i] = -1;
			} else {
				ans[i] = entry.getValue() == Integer.MAX_VALUE ? -1 : entry.getValue();
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution0 so = new Solution0();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
		so.debug6();
		so.debug7();
	}

}
